首先,我们得知道过原点与两点的抛物线解析式:
设该函数解析式为 且过 三点。
由函数过 得 。
函数解析式为
综上所述,函数解析式为
剩下的就容易处理了。
#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
#define eps 1e-8
#define Paird pair<double,double>
const int MAXN = 20;
int t , n , m , Ans , s;
struct node{
double x , y;
}dex[ MAXN + 5 ] , fun[ MAXN + 5 ] , lone[ MAXN + 5 ];
Paird calc( node a , node b ) {
double A = ( b.x * a.y - a.x * b.y ) / ( a.x * b.x * ( a.x - b.x ) ) , B = ( b.y * a.x * a.x - a.y * b.x * b.x ) / ( a.x * b.x * ( a.x - b.x ) );
return { A , B };
}
void dfs( int x , int num , int lon ) {
if( num + lon >= Ans ) return;
if( x == n + 1 ) {
Ans = num + lon; //使用的鸟+剩下的猪各需一只鸟
return;
}
for( int i = 1 ; i <= num ; i ++ ) //看这只猪能否被之前的一只鸟击中
if( fabs( fun[ i ].x * dex[ x ].x * dex[ x ].x + fun[ i ].y * dex[ x ].x - dex[ x ].y ) < eps ) {
dfs( x + 1 , num , lon );
return;
}
for( int i = 1 ; i <= lon ; i ++ ) { //与之前剩下的一只猪组成抛物线
if( fabs( dex[ x ].x - lone[ i ].x ) < eps ) continue;
Paird s = calc( dex[ x ] , lone[ i ] );
if( s.first < 0 ) {
fun[ num + 1 ] = { s.first , s.second };
node tmp[ MAXN + 5 ];
for( int k = i ; k <= lon ; k ++ )
tmp[ k ] = lone[ k ];
for( int k = i ; k < lon ; k ++ )
lone[ k ] = lone[ k + 1 ];
dfs( x + 1 , num + 1 , lon - 1 );
for( int k = i ; k <= lon ; k ++ )
lone[ k ] = tmp[ k ];
}
}
lone[ lon + 1 ] = dex[ x ]; //作为剩下的一只猪
dfs( x + 1 , num , lon + 1 );
}
int main( ) {
scanf("%d",&t);
while( t -- ) {
scanf("%d %d",&n,&m); Ans = n;
for( int i = 1 ; i <= n ; i ++ )
scanf("%lf %lf",&dex[ i ].x,&dex[ i ].y);
dfs( 1 , 0 , 0 );
printf("%d\n",Ans);
}
return 0;
}